package cyc2018.贪心思想;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 无重叠区间
 */
public class Test435 {


    static class Interval {
        int start;
        int end;

        Interval() {
            start = 0;
            end = 0;
        }

        Interval(int s, int e) {
            start = s;
            end = e;
        }
    }


    public static int eraseOverlapIntervals(Interval[] intervals) {
        if (intervals.length == 0) {
            return 0;
        }
        // 按照区间 end 值排序。每次选择结尾最小，并且和前一个区间不重叠的区间。
        Arrays.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                return o1.end - o2.end;
            }
        });
        int cnt = 0;
        int end = intervals[0].end;
        // 先计算最多能组成的不重叠区间个数，然后用区间总个数减去不重叠区间的个数。
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i].start < end) {
                continue;
            }
            end = intervals[i].end;
            cnt++;
        }

        return intervals.length - 1 - cnt;
    }

    public static void main(String[] args) {
        Interval[] intervals = {new Interval(1,2), new Interval(2,3), new Interval(3,4), new Interval(1,3)};
        int i = eraseOverlapIntervals(intervals);
        System.out.println(i);
    }

}
